package datastructure;


import utils.TreeNode;

import java.util.*;

import static utils.TreeNode.buildTree;
import static utils.TreeNode.show;


/**
 * @Author ZhangCuirong
 * @Date 2025/7/31 15:46
 * @description:
 */
public class BinaryTreeTraversal {

    // 先序遍历：根 -> 左 -> 右
    public static void preorder(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.val + " "); // 先访问根节点

            // 右子树先入栈，左子树后入栈（栈是先进后出）
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
    }

    // 中序遍历：左 -> 根 -> 右
    public static void inorder(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            // 先把左子树全部入栈
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }

            // 弹出栈顶元素（最左节点）并访问
            curr = stack.pop();
            System.out.print(curr.val + " ");

            // 转向右子树
            curr = curr.right;
        }
    }

    // 后序遍历：左 -> 右 -> 根（用两个栈实现，便于记忆）
    public static void postorder(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(root);

        // 第一个栈弹出顺序：根 -> 右 -> 左
        while (!stack1.isEmpty()) {
            TreeNode node = stack1.pop();
            stack2.push(node); // 存入第二个栈

            // 左子树先入栈1，右子树后入栈1
            if (node.left != null) stack1.push(node.left);
            if (node.right != null) stack1.push(node.right);
        }

        // 第二个栈弹出顺序：左 -> 右 -> 根
        while (!stack2.isEmpty()) {
            System.out.print(stack2.pop().val + " ");
        }
    }



    // 测试
    public static void main(String[] args) {
        // 层序序列：1,2,3,4,5,-1,-1（-1表示对应位置为空节点）
        int[] levelOrder = {1, 2, 3, -1, 5, 9, -1};

        // 构建二叉树
        TreeNode root = buildTree(levelOrder);
        show(root);

        // 验证：用之前的遍历方法输出，检查是否符合预期
        System.out.print("先序遍历: ");
        BinaryTreeTraversal.preorder(root); // 预期：1 2 4 5 3

        System.out.print("\n中序遍历: ");
        BinaryTreeTraversal.inorder(root);  // 预期：4 2 5 1 3

        System.out.print("\n后序遍历: ");
        BinaryTreeTraversal.postorder(root); // 预期：4 5 2 3 1
    }
}
